package com.gitee.feizns.explore.data_structure.tree.bs.mid;

/**
 * @author feizns
 * @since 2020/3/18
 */
public class BtreeGameWinningMove {

    public static void main(String[] args) {

    }

    public static boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        if ( root.val == x )
            return num(root.left) != num(root.right);
        TreeNode xNode = find(root, x);
        int lef = num(xNode.left);
        if ( lef >= n / 2 )
            return true;
        int rig = num(xNode.right);
        if ( rig >= n / 2 )
            return true;
        return lef + rig + 1 >= n / 2;
    }

    private static TreeNode find(TreeNode node, int x) {
        if ( node != null ) {
            if ( node.val == x )
                return node;
            TreeNode lef = find(node.left, x);
            if ( lef != null )
                return lef;
            return find(node.right, x);
        }
        return null;
    }

    private static int num(TreeNode node) {
        return node != null ? num(node.left) + num(node.right) + 1 : 0;
    }

}
